1. Field of the Invention
The present invention generally relates to optically encoded symbologies, and more particularly relates to methods and systems for encoding and decoding data into a two-dimension symbology.
2. Description of the Related Art
In today's high-technology world, more and more operations are performed automatically by computers. This increasing demand for automation has created strong demands for new technologies. Bar-code is one of the technologies used for automating data entry.
A bar-code symbol is a pattern containing a series of bars of various widths and spaced apart from one another by spaces of various widths, the bars and spaces have different light reflective properties representing strings of binary ones and zeros. Bar-code symbols are printed directly on a substance or on labels attached to the object. The bar-code symbols are typically read by optical techniques, such as laser beams, Charge-Coupled. Device (CCD) or Contact Image Sensor (CIS) cameras. A typical laser-based bar-code reader uses a photo-sensor to convert bars and spaces into an electrical signal as it moves across a bar-code. The reader then measures the relative widths of bars and spaces, translates the different pattern back into regular characters, and spends them on to a computer or portable terminal for further processing. There is a minimum width for these bars and spaces to be decoded properly by scanners. The minimum width is called a “unit” or “module”. The spaces and bars are multiples of the “unit” or “module”.
The conventional bar-code described above is one-dimensional. The information encoded in one-dimension (1D) bar-code is represented only by the widths of bars and spaces, which extends in a single dimension. All the bars and spaces have a uniform height in their vertical direction, thus the information only stored in the horizontal direction of a 1D bar-code. Generally a 1D bar-code is widely used as indices to associate physical objects with larger database containing detailed information. Because of the single dimension, 1D bar-code can only store very limited amount of information, for example, a zip code, a social security number or a serial number.
As the demand for information technologies grows, there is a strong interest in eliminating the associated database and storing more information into the symbology itself. As a result of this demand, the two-dimensional (2D) bar-code technologies have emerged from the extension of the 1D bar-code. The 2D bar-code symbologies are generally square or rectangular patterns that encode data in two dimensions. They fall into two general categories: “stacked bar-code” is constructed like a layer cake of 1D bar-code stacked one on top of another; “matrix bar-code” is built on a true two dimensional matrix.
One of the most commonly used “stacked bar-code” is PDF417 as shown in FIG. 1A. The detailed descriptions of PDF417 can be found in U.S. Pat. No. 5,304,786. PDF417 contains a number of code segments. Each consists of 4 bars and 4 spaces with total width of 17 modules, hence the name PDF417. It has a high tolerance for damaged symbology when high level of error correction is built in the symbol. Theoretically PDF417 can store up to 2000 characters per symbol, however the practical limit is no more than 350 characters. It is required to print PDF symbol with high resolution printer such as laser or thermal transfer printers. PDF417 can be read by cameras (CCD or CMOS), and a modified handheld laser or CIS scanner.
QR Code (Quick Response Code) is an example of a “matrix bar-code” developed by Nippondenso ID Systems. As shown in FIG. 1B, a QR Code symbol is square in shape and can easily be identified by its finder pattern of nested alternating dark and light squares at three corners of the symbol. Due to the finder pattern, a QR Code symbol can be read very rapidly with CCD array cameras. The drawback is the size, which is 177 modules squared, maximum. The corresponding maximum storage capacity is 2956 bytes with encoded with 750 bytes lowest level error correction code.
Scanners based on CCD or CIS cameras are particularly suitable for reading a 2D bar-code. Generally, scanners convert light (which human can see) into 0s and 1s (which a computer can process). In other words, scanners convert data from analogue format into digital format. All scanners work on the same principle of reflectance or transmission. A scanning object to be scanned is placed before a scanner which comprises a light source and a sensor. The amount of light reflected by or transmitted through the scanning object is picked up by the sensor and then converted to a signal proportional to the light intensity.
One of the factors affecting the scanner performance is the scan resolution. The scan resolution relates to the fineness of detail that a scanner can achieve, and is usually measured in dots per inch (dpi). The more dots per inch a scanner can resolve, the more detail the resulting image will have. A scanner typically has a photoelement for each pixel. A scanner claiming a horizontal optical resolution of 600 dpi is alternatively referred to as 600 pixels per inch (ppi), and this is also referred as scanner's x-direction resolution. For a scanner having a maximum scanning width of 8.5 inches, there is an array of 5100 photoelements in the scan head. The scan head is mounted on a transport which is moved across a scanning object. Although the process may appear to be a continuous movement, the head moves a fraction of an inch at a time, taking a reading between each movement. The number of physical elements in a sensor array determines the horizontal sampling rate and the number of steps per inch determines the vertical sampling rate, which is referred as scanner's y-direction resolution. The scanners resolution is based on its x-direction and y-direction resolutions.
It would be desirable to have a new 2D bar-code with following characteristics storing much more information, built-in redundancy, multiple levels of damage protection, flexible width and length symbol, and allowing hand-held line-based contact or non-contact scanning.
With proliferation of hand operating a scanning devices, it is preferred to scan a 2D bar-code with hand-held scanners. However, there exist a few problems. A phenomena known as the loss of vertical synchronization 200 in scanning 2D bar-code symbols due to the limited height of elements is shown in FIG. 2. A 2D bar-code 210 is overlapped with a set of parallel scan lines 220. Generally, the angle between scan line 220 and the horizontal axis of the bar-code 210 is non-zero for a hand-held scanning device. Due to the limited height of bar-code elements, certain scan lines 230 cut across two rows of bar-code elements. As a result, these scan lines 230 are not useful. It would be desirable to have a method to decode the 2D bar-code avoiding the loss of synchronization problem. It would also be desirable to decode the 2D bar-code efficiently and effectively.